#include<stdio.h> 
#include<stdlib.h> 

/*图的定义*/
#define MaxVertexNum 100 /*最大顶点数设为100*/ 
#define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/ 
typedef int Vertex;  /*用顶点下标表示顶点，为整型*/
typedef int WeightType; /*边的权值设为整型*/ 
/*边的定义*/
typedef struct ENode*PtrToENode; 
struct ENode{ 
    Vertex V1,V2; /*有向边<V1,V2>*/ 
    WeightType Weight;/*权重*/ 
}; 
typedef PtrToENode Edge; 
/*图结点的定义*/ 
typedef struct GNode*PtrToGNode; 
struct GNode{
    int Nv;/*顶点数*/ 
    int Ne;/*边数 */ 
    WeightType G[MaxVertexNum] [MaxVertexNum];/*邻接矩阵*/
};

typedef PtrToGNode MGraph;/*以邻接矩阵存储的图类型*/ 

MGraph CreateGraph(int VertexNum); 
void InsertEdge (MGraph Graph,Edge E);
MGraph BuildGraph(); 
void Floyd(MGraph Graph,WeightType D[][MaxVertexNum]); 
WeightType FindMaxDist (WeightType D[][MaxVertexNum], Vertex i,int N); 
void FindAnimal(MGraph Graph);
int main()
{
    MGraph G=BuildGraph();
    FindAnimal(G);
    return 0;
}
MGraph CreateGraph(int VertexNum)
{
    //初始化一个有VertexNum个顶点但没有边的图
    Vertex V,W;
    MGraph Graph;
    Graph=(MGraph)malloc(sizeof(struct GNode));
    Graph->Nv =VertexNum; 
    Graph->Ne =0; 
    /*初始化邻接矩阵*/ 
    for(V=0;V<Graph->Nv;V++)
        for(W=0;W<Graph->Nv;W++) 
            Graph->G[V][W]=INFINITY; 
    return Graph; 
}
void InsertEdge (MGraph Graph,Edge E){
    /*插人边<V1,V2>*/ 
    Graph->G[E->V1][E->V2]=E->Weight; 
    /*若是无向图，还要插人边<V2,V1>*/ 
    Graph->G[E->V2][E->V1]=E->Weight; 
}
MGraph BuildGraph() 
{
    MGraph Graph;
    Edge E; 
    int Nv,i; 
    scanf ("%d",&Nv); /*读人顶点个数*/ 
    Graph=CreateGraph(Nv);/*初始化有Nv个顶点但没有边的图*/ 
    scanf ("%d",&(Graph->Ne)); /*读人边数*/
    if(Graph->Ne !=0){/*如果有边*/
        E=(Edge)malloc(sizeof (struct ENode));/*建立边结点*/ 
        /*读人边，格式为“起点终点权重”，插人邻接矩阵*/
        for (i=0;i<Graph->Ne;i++){
            scanf ("%d %d %d",&E->V1,&E->V2,&E->Weight);    
            E->V1--;E->V2--;/*输人编号从1开始*/
            InsertEdge(Graph,E); 
        }
    }
    return Graph;
}
 
void Floyd(MGraph Graph,WeightType D[][MaxVertexNum]) 
{
    Vertex i,j,k; 
    /*初始化*/ 
    for (i=0;i<Graph->Nv;i++) 
        for (j=0;j<Graph->Nv;j++) 
            D[i][j]=Graph->G[i][j];
    for (k=0;k<Graph->Nv;k++) 
        for(i=0;i<Graph->Nv;i++) 
            for (j=0;j<Graph->Nv;j++) 
                if (D[i][k]+D[k][j]<D[i][j]) 
                    D[i][j]=D[i][k]+D[k][j];
}
WeightType FindMaxDist(WeightType D[][MaxVertexNum],Vertex i,int N) /*找出i到其他动物的最长距离*/ 
{
    WeightType MaxDist; 
    Vertex j; 
    MaxDist =0; 
    for(j=0;j<N;j++) 
        if(i!=j && D[i][j]>MaxDist)
            MaxDist=D[i][j]; 
    return MaxDist; 
}

void FindAnimal(MGraph Graph) 
{
    WeightType D[MaxVertexNum][MaxVertexNum],MaxDist,MinDist; 
    Vertex Animal,i; 
    Floyd(Graph, D); 
    MinDist =INFINITY; 
    for(i=0;i<Graph->Nv;i++){ 
        MaxDist =FindMaxDist (D,i,Graph->Nv); 
        if (MaxDist ==INFINITY){/*说明有从i无法变出的动物*/ 
            printf("0\n"); 
            return; 
        }
        if (MinDist >MaxDist){ /*找到最长距离更小的动物*/ 
            MinDist =MaxDist;Animal =i+1;/*更新距离，记录编号*/
        }
    } 
    printf("%d %d\n",Animal,MinDist); 
}